Graphics rendering refers generally to the process of generating a two-dimensional image from graphical models. A graphical model defines attributes of a real or imaginary object which are to be represented in a rendered image. These attributes include, for example, color, shape, and position of an object in a graphics scene. In the process of rendering these models, a graphics system generates a display image, which typically includes an array of pixel data. A pixel is a point or picture element in a display device, and in the context of graphics processing, also corresponds to a point in the two dimensional space to which the graphical models are rendered. The pixel data of a rendered image includes one or more data values describing attributes of a pixel used to display it. For instance, this pixel data can include intensity values for color components. These intensity values are then used to display the array of pixels comprising an image on physical output device such as a raster display device.
Graphics processing is often classified by the dimension of the models to be rendered to an image. For instance, two-dimensional graphics processing ("2D graphics") refers to the generation of an image from graphical models having two dimensions (x and y coordinates) and three dimensional graphics processing ("3D" graphics) refers the processing of three-dimensional models.
Graphics processing can also be classified as "real time" which means that 1) the display image is updated so that the user perceives continuous motion of the objects in the scene, and 2) there is minimal and predictable "transport delay" between user input, which changes the position of objects or the viewpoint of the scene, and the display of an image in response to this input. To achieve this effect, a scene, or objects in the scene, must be rendered within a predefined period of time.
In 3D graphics applications, objects in a scene are represented by 3D graphical models, which include geometric data used to model the surface and position of the objects, and visual attributes used to model the appearance of the objects. There are a number of ways that a geometric model can represent the surface of a 3D object such as with polygon meshes, parametric surfaces, or quadratic surfaces. Using a polygon mesh, for example, the surface of an object is modeled with several interconnected polygons. The surface elements, in this case polygons, are referred to as geometric primitives. Visual attributes such as red, green, and blue color data, and possibly other model data is stored at the vertices of the polygon.
In the rendering process, the geometric primitives corresponding to objects in a scene are processed to generate a display image. In the context of 3D graphics, the rendering process includes two primary steps: transforming the graphical models in a scene, and rasterizing the geometric primitives in the models to generate pixel data.
The rendering process typically begins by transforming the vertices of the geometric primitives to prepare the model data for the rasterizing step. While the specific details of the transformation phase varies, a few examples will illustrate the process. The modeling transform, in some systems, is used to convert the vertices of a model from the model's local coordinate to world coordinates, the coordinates in which a complete scene is represented. The next step is to determine potentially visible objects in a 3D space referred to as the view volume. This step is commonly performed in view reference coordinates, which describes object locations relative to a viewpoint or eyepoint. Objects that are not potentially visible at this stage can be disregarded while objects that are least partially in the view volume are "clipped" to the view volume.
After transforming the objects, the geometric primitives for the objects are "rasterized." Rasterizing generally refers to the process of computing a pixel value or values for a pixel in the view space based on data from the geometric primitives that project onto or "cover" the pixel. Rasterizing is sometimes referred to as "tiling" because of the analogy to tiling a floor. Imagine that the pixels are square elements or tiles, and that a polygon is the floor plan. The rasterizing step includes "tiling" this floor plan by computing pixel values for the pixels or "tiles" within the polygon.
While there are a number of ways to rasterize a geometric primitive, this process generally involves computing a pixel intensity value or values based on the data from polygons that project onto a pixel. For example, color values stored at the vertices of a polygon can be interpolated to find a color value at a given pixel. During this process, lighting and shading models can also be used to compute pixel values for pixels across the surface of the polygon.
From the tiling analogy above, it is clear that discrete pixels cannot precisely represent continuous surfaces. For example, a polygon may only partially cover a pixel region. In this case, the edge or edges of a polygon cross over the pixel region. If the pixel were approximated as being fully covered by this polygon, anomalies such as jaggy edges in the rendered image would likely result. A technique known generally as antialiasing attempts to address this problem. In general, antialiasing is used to compute pixel intensities for partially covered pixels to reduce the discontinuities introduced by representing a continuous object with a discrete array of pixels.
In a given 3D graphics scene, a number of polygons may project onto the same area of the view space, and some of these polygons may occlude others. As such, some primitives may not be "visible" in the scene. Hidden surface removal is the process of determining which objects or portions of objects are, and conversely, are not visible in the scene. Like the process of rasterizing geometry, there are a number of approaches to hidden surface removal. Some approaches to hidden surface removal require additional processing overhead before the rasterizing step. Examples of these types of approaches include: 1) sorting primitives and then rasterizing the primitives in back to front order, and 2) sorting primitives in depth order and then clipping the primitives relative to each other to eliminate hidden portions of the primitives. Of course there are a number of variations to these examples as well as a variety of additional examples.
These approaches are generally not preferred because the additional computational complexity consumes more processing resources. For real time systems where objects are in motion from scene to scene, the computations required for these approaches makes them untenable alternatives.
In other approaches, the primitives are not sorted before scan conversion, but instead, the pixel data generated from the scan conversion process includes depth values used to perform hidden surface removal. The z-buffer algorithm is one such approach. A z-buffer includes an array having elements for storing pixel data including depth values for every pixel location in a display image. As geometric primitives are rasterized, the depth value for newly generated pixel data is compared with a depth value of pixel data stored in the z buffer. If the newly generated pixel data is closer to the viewpoint, it is written over the current values in the z-buffer for the corresponding pixel location. If not, it is disregarded.
The primary advantages of the z-buffer approach are computational speed and simplicity. However, by itself, the z-buffer approach provides no support for dealing with partially covered pixels or translucent pixels.
The general z-buffer approach has been improved to support sophisticated antialiasing and translucency computations to improve image quality. One improvement is known as the A-Buffer as described in Carpenter, L., "The A-Buffer, An Antialiased Hidden Surface Method. Computer Graphics 18, 3 (July 1984), 103-108. In this approach, polygons are clipped into fragments at the boundaries of a pixel region. For example, assume, a pixel is represented as a square. If 3-sided polygon (triangle) partially covers this square, a pixel fragment is generated to represent the portion of the triangle covering the square. A bit mask, created by exclusive ORing masks representing polygons edges, is used to describe how a polygon partially covers the pixel region.
After all polygons that can potentially intersect a pixel have been processed, the final color values are computed for the pixel using a depth sorted list of fragments. We refer to the processing of a fragments to compute these pixel values as "resolving" or "resolution." The bit mask for the nearest fragment is used to clip the bit mask of fragments farther from the viewpoint. For visible fragments, the contribution of a fragment to the pixel color is weighted by the fragment's area. For fragments with transparency, the process of clipping fragments proceeds recursively for fragments behind the transparent fragment. The final color for a pixel is computed by blending a contribution of the portion of the pixel covered by fragment(s) with the portion not covered by fragments.
While the A-buffer approach can support sophisticated anti-aliasing and translucency computations, the challenge is implementing a working system. The Carpenter paper describes that a software implementation of the A-Buffer approach has been used to generate high quality pictures. A software implementation tends to have a number of drawbacks. One drawback to a software implementation is performance. Software systems typically cannot run fast enough to support real time constraints. Another drawback is cost. A computer system fast enough to carry out the A-buffer approach under real time constraints is very expensive.
One particular challenge to implementing the A-Buffer approach is supporting pixel resolution of fragment lists while also achieving real time rendering rates. The inventors know of no system that has successfully performed pixel resolution on pixel fragment lists in a real time system.